{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Remove Colored Pieces if Both Neighbors are the Same Color"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #math #string #game-theory"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数学 #字符串 #博弈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: winnerOfGame"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #如果相邻两个颜色均相同则删除当前颜色"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>总共有 <code>n</code>&nbsp;个颜色片段排成一列，每个颜色片段要么是&nbsp;<code>'A'</code>&nbsp;要么是&nbsp;<code>'B'</code>&nbsp;。给你一个长度为&nbsp;<code>n</code>&nbsp;的字符串&nbsp;<code>colors</code>&nbsp;，其中&nbsp;<code>colors[i]</code>&nbsp;表示第&nbsp;<code>i</code>&nbsp;个颜色片段的颜色。</p>\n",
    "\n",
    "<p>Alice 和 Bob 在玩一个游戏，他们 <strong>轮流</strong>&nbsp;从这个字符串中删除颜色。Alice <strong>先手</strong>&nbsp;。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果一个颜色片段为 <code>'A'</code>&nbsp;且 <strong>相邻两个颜色</strong>&nbsp;都是颜色 <code>'A'</code>&nbsp;，那么 Alice 可以删除该颜色片段。Alice&nbsp;<strong>不可以</strong>&nbsp;删除任何颜色&nbsp;<code>'B'</code>&nbsp;片段。</li>\n",
    "\t<li>如果一个颜色片段为 <code>'B'</code>&nbsp;且 <strong>相邻两个颜色</strong>&nbsp;都是颜色 <code>'B'</code>&nbsp;，那么 Bob 可以删除该颜色片段。Bob <strong>不可以</strong>&nbsp;删除任何颜色 <code>'A'</code>&nbsp;片段。</li>\n",
    "\t<li>Alice 和 Bob <strong>不能</strong>&nbsp;从字符串两端删除颜色片段。</li>\n",
    "\t<li>如果其中一人无法继续操作，则该玩家 <b>输</b>&nbsp;掉游戏且另一玩家 <strong>获胜</strong>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>假设 Alice 和 Bob 都采用最优策略，如果 Alice 获胜，请返回&nbsp;<code>true</code>，否则 Bob 获胜，返回<em>&nbsp;</em><code>false</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>colors = \"AAABABB\"\n",
    "<b>输出：</b>true\n",
    "<b>解释：</b>\n",
    "A<em><strong>A</strong></em>ABABB -&gt; AABABB\n",
    "Alice 先操作。\n",
    "她删除从左数第二个 'A' ，这也是唯一一个相邻颜色片段都是 'A' 的 'A' 。\n",
    "\n",
    "现在轮到 Bob 操作。\n",
    "Bob 无法执行任何操作，因为没有相邻位置都是 'B' 的颜色片段 'B' 。\n",
    "因此，Alice 获胜，返回 true 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>colors = \"AA\"\n",
    "<b>输出：</b>false\n",
    "<strong>解释：</strong>\n",
    "Alice 先操作。\n",
    "只有 2 个 'A' 且它们都在字符串的两端，所以她无法执行任何操作。\n",
    "因此，Bob 获胜，返回 false 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>colors = \"ABBBBBBBAAA\"\n",
    "<b>输出：</b>false\n",
    "<strong>解释：</strong>\n",
    "ABBBBBBBA<em><strong>A</strong></em>A -&gt; ABBBBBBBAA\n",
    "Alice 先操作。\n",
    "她唯一的选择是删除从右数起第二个 'A' 。\n",
    "\n",
    "ABBBB<strong><em>B</em></strong>BBAA -&gt; ABBBBBBAA\n",
    "接下来轮到 Bob 操作。\n",
    "他有许多选择，他可以选择任何一个 'B' 删除。\n",
    "\n",
    "然后轮到 Alice 操作，她无法删除任何片段。\n",
    "所以 Bob 获胜，返回 false 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;=&nbsp;colors.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>colors</code>&nbsp;只包含字母&nbsp;<code>'A'</code>&nbsp;和&nbsp;<code>'B'</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [remove-colored-pieces-if-both-neighbors-are-the-same-color](https://leetcode.cn/problems/remove-colored-pieces-if-both-neighbors-are-the-same-color/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [remove-colored-pieces-if-both-neighbors-are-the-same-color](https://leetcode.cn/problems/remove-colored-pieces-if-both-neighbors-are-the-same-color/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"AAABABB\"', '\"AA\"', '\"ABBBBBBBAAA\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def winnerOfGame(self, colors: str) -> bool:\n",
    "        count3A = 0\n",
    "        count3B = 0\n",
    "        curA = 0\n",
    "        curB = 0\n",
    "        for c in colors:\n",
    "            if c == 'A':\n",
    "                curA += 1\n",
    "                if curB >= 3:\n",
    "                    count3B += curB - 2\n",
    "                curB = 0\n",
    "            else:\n",
    "                curB += 1\n",
    "                if curA >= 3:\n",
    "                    count3A += curA - 2\n",
    "                curA = 0\n",
    "        if curA >= 3:\n",
    "            count3A += curA - 2\n",
    "        if curB >= 3:\n",
    "            count3B += curB - 2\n",
    "    \n",
    "        return count3A > count3B\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def groupby(A:Iterable, key=lambda x:x):\n",
    "    \"\"\" group A by its value\n",
    "    can also be used to split string\n",
    "    \"\"\"\n",
    "    n = len(A)\n",
    "    i = 0\n",
    "    for j in range(1, n+1):\n",
    "        if j==n or key(A[i])!=key(A[j]):\n",
    "            if j-i>=2:\n",
    "                yield i,j\n",
    "            i = j\n",
    "            \n",
    "class Solution:\n",
    "    def winnerOfGame(self, A: str) -> bool:\n",
    "        na = nb = 0\n",
    "        for l,r in groupby(A):\n",
    "            if A[l] == 'A':\n",
    "                na += (r-l)-2\n",
    "            else:\n",
    "                nb += (r-l)-2\n",
    "        \n",
    "        return na>nb"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def winnerOfGame(self, colors: str) -> bool:\n",
    "        # 统计A和B的连续片段\n",
    "        n = len(colors)\n",
    "        cnta = 0\n",
    "        cntb = 0\n",
    "        ra =0\n",
    "        rb = 0\n",
    "        for i in range(n):\n",
    "            if colors[i]=='A':\n",
    "                cnta+=1\n",
    "                if cnta>=3:\n",
    "                    ra+=1\n",
    "                cntb=0\n",
    "            else:\n",
    "                cntb+=1\n",
    "                if cntb>=3:\n",
    "                    rb+=1\n",
    "                cnta=0\n",
    "        return ra > rb"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def winnerOfGame(self, colors: str) -> bool:\n",
    "        a, b = 0, 0\n",
    "        cur = 0\n",
    "        for c in colors:\n",
    "            if c == 'A':\n",
    "                cur += 1\n",
    "            else:\n",
    "                a += max(0, cur - 2)\n",
    "                cur = 0\n",
    "        a += max(0, cur - 2)\n",
    "        cur = 0\n",
    "        for c in colors:\n",
    "            if c == 'B':\n",
    "                cur += 1\n",
    "            else:\n",
    "                b += max(0, cur - 2)\n",
    "                cur = 0\n",
    "        b += max(0, cur - 2)\n",
    "        if a <= b:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def winnerOfGame(self, colors: str) -> bool:\n",
    "        count = 0\n",
    "        for i in range(len(colors)-2):\n",
    "            k = colors[i:i+3]\n",
    "            if k == 'AAA':\n",
    "                count += 1\n",
    "            if k =='BBB':\n",
    "                count -= 1\n",
    "        return count>0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def winnerOfGame(self, colors: str) -> bool:\n",
    "        #只有AAA，AAAA，AAAAA这种子串才可以裁剪\n",
    "        #裁剪1，2，3次\n",
    "        #AB不会相互影响，我们只要统计这些子串，然后比较谁的次数多即可(滑动窗口)\n",
    "        #numA>numB ==> Alice win\n",
    "        n = len(colors)\n",
    "        score = {'A':0,'B':0}\n",
    "        flag = colors[0]\n",
    "        j = 0\n",
    "        for i in range(1,n+1):\n",
    "            if i==n or colors[i] != colors[i-1]:\n",
    "                score[colors[i - 1]] += max(0, i - j - 2)\n",
    "                j = i\n",
    "        return score['A'] > score['B']\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    import re\n",
    "    def winnerOfGame(self, colors: str) -> bool:\n",
    "\n",
    "        alice = re.findall(r'A(A+)A', colors)\n",
    "        bob = re.findall(r'B(B+)B', colors)\n",
    "\n",
    "        return len(''.join(alice)) > len(''.join(bob))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def winnerOfGame(self, colors: str) -> bool:\n",
    "        cnt = {'A': 0, 'B': 0}\n",
    "        stack = []\n",
    "        for color in colors:\n",
    "            if len(stack) > 1 and stack[-1] == stack[-2] == color:\n",
    "                stack.pop()\n",
    "                cnt[color] += 1\n",
    "            stack.append(color)\n",
    "        if cnt['A'] > cnt['B']:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def winnerOfGame(self, colors: str) -> bool:\n",
    "        # A >= B and A != 0  A 赢\n",
    "        ansa = ansb = 0\n",
    "        \n",
    "        n = len(colors)\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            if i >= 2 and colors[i-1] == colors[i-2] == colors[i]:\n",
    "                start = i\n",
    "                i = i+1\n",
    "                while i < n and colors[i] == colors[i-1]:\n",
    "                    i += 1\n",
    "                    \n",
    "                if colors[start] == 'A':\n",
    "                    ansa += i-start\n",
    "                else:\n",
    "                    ansb += i-start\n",
    "            else:\n",
    "                i += 1\n",
    "        print(ansa,ansb)\n",
    "        return ansa > ansb\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def winnerOfGame(self, colors: str) -> bool:\n",
    "        As = 0\n",
    "        Bs = 0\n",
    "        last_color = colors[0]\n",
    "        last_idx = 0\n",
    "        for i in range(1, len(colors)):\n",
    "            if colors[i] == last_color and i != len(colors)-1:\n",
    "                continue\n",
    "            if colors[i] != last_color:\n",
    "                if last_color == 'A':\n",
    "                    As += max(0, i - last_idx - 2)\n",
    "                else:\n",
    "                    Bs += max(0, i - last_idx - 2)\n",
    "                last_color = colors[i]\n",
    "                last_idx = i\n",
    "            if i == len(colors)-1:\n",
    "                if last_color == 'A':\n",
    "                    As += max(0, i - last_idx + 1 - 2)\n",
    "                else:\n",
    "                    Bs += max(0, i - last_idx + 1 - 2)\n",
    "        print(As, Bs)\n",
    "        return As > Bs\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def winnerOfGame(self, colors: str) -> bool:\n",
    "        def cal(colors, ch):\n",
    "            n = len(colors)\n",
    "            i = 0\n",
    "            ans = 0\n",
    "            while i < n:\n",
    "                if colors[i] != ch:\n",
    "                    i += 1\n",
    "                    continue\n",
    "                l = i\n",
    "                i += 1\n",
    "                while i < n and colors[i] == ch:\n",
    "                    i += 1\n",
    "                ans += max(0, i - l - 2)\n",
    "            return ans\n",
    "        return cal(colors, 'A') > cal(colors, \"B\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def winnerOfGame(self, colors: str) -> bool:\n",
    "        # 正则\n",
    "        ca = cb = 0\n",
    "        for i in re.findall('A{3,}', colors):\n",
    "            ca += len(i)-2\n",
    "        for i in re.findall('B{3,}', colors):\n",
    "            cb += len(i)-2\n",
    "        return ca - cb >= 1\n",
    "\n",
    "        # 拆分计数法\n",
    "        count = [0,0]\n",
    "        c = 'BA'\n",
    "        for i in range(2):\n",
    "            lst = colors.split(c[i])\n",
    "            for ss in lst:\n",
    "                if len(ss) > 2:\n",
    "                    count[i] += len(ss) - 2\n",
    "        return count[0] > count[1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def winnerOfGame(self, colors: str) -> bool:\n",
    "        if len(colors)<3:\n",
    "            return False\n",
    "        a=0\n",
    "        b=0\n",
    "        c1=list(colors)\n",
    "        for i in range(2,len(c1)):\n",
    "            if c1[i]==c1[i-1]==c1[i-2]:\n",
    "                if c1[i]=='A':a+=1\n",
    "                if c1[i]=='B':b+=1\n",
    "        if a>b :return True\n",
    "        else:return False         \n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
